Automata Techniques for Epistemic Protocol Synthesis
Identifieur interne : 000C19 ( Main/Exploration ); précédent : 000C18; suivant : 000C20Automata Techniques for Epistemic Protocol Synthesis
Auteurs : Guillaume Aucher [France] ; Bastien Maubert [France] ; Sophie Pinchinat [France]Source :
Abstract
In this work we aim at applying automata techniques to problems studied in Dynamic Epistemic Logic, such as epistemic planning. To do so, we first remark that repeatedly executing ad infinitum a propositional event model from an initial epistemic model yields a relational structure that can be finitely represented with automata. This correspondence, together with recent results on uniform strategies, allows us to give an alternative decidability proof of the epistemic planning problem for propositional events, with as by-products accurate upper-bounds on its time complexity, and the possibility to synthesize a finite word automaton that describes the set of all solution plans. In fact, using automata techniques enables us to solve a much more general problem, that we introduce and call epistemic protocol synthesis.
Url:
DOI: 10.4204/EPTCS.146.13
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: 001051
- to stream Hal, to step Curation: 001051
- to stream Hal, to step Checkpoint: 000B61
- to stream Main, to step Merge: 000C25
- to stream Main, to step Curation: 000C19
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Automata Techniques for Epistemic Protocol Synthesis</title>
<author><name sortKey="Aucher, Guillaume" sort="Aucher, Guillaume" uniqKey="Aucher G" first="Guillaume" last="Aucher">Guillaume Aucher</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-419153" status="VALID"><idno type="RNSR">198018249C</idno>
<orgName>Inria Rennes – Bretagne Atlantique </orgName>
<desc><address><addrLine>Campus de beaulieu35042 Rennes cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/centre/rennes</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-300009" type="direct"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Maubert, Bastien" sort="Maubert, Bastien" uniqKey="Maubert B" first="Bastien" last="Maubert">Bastien Maubert</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno>
<idno type="RNSR">198912571S</idno>
<idno type="IdUnivLorraine">[UL]RSI--</idno>
<orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<orgName type="acronym">LORIA</orgName>
<date type="start">2012-01-01</date>
<desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-413289" type="direct"></relation>
<relation name="UMR7503" active="#struct-441569" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-300009" type="direct"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-413289" type="direct"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno>
<idno type="IdUnivLorraine">[UL]100--</idno>
<orgName>Université de Lorraine</orgName>
<orgName type="acronym">UL</orgName>
<date type="start">2012-01-01</date>
<desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-lorraine.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR7503" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Nancy</settlement>
<settlement type="city">Metz</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Université de Lorraine</orgName>
</affiliation>
</author>
<author><name sortKey="Pinchinat, Sophie" sort="Pinchinat, Sophie" uniqKey="Pinchinat S" first="Sophie" last="Pinchinat">Sophie Pinchinat</name>
<affiliation wicri:level="1"><hal:affiliation type="institution" xml:id="struct-105160" status="VALID"><orgName>Université de Rennes 1</orgName>
<orgName type="acronym">UR1</orgName>
<desc><address><addrLine>2 rue du Thabor - CS 46510 - 35065 Rennes cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-rennes1.fr/</ref>
</desc>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-01098740</idno>
<idno type="halId">hal-01098740</idno>
<idno type="halUri">https://hal.inria.fr/hal-01098740</idno>
<idno type="url">https://hal.inria.fr/hal-01098740</idno>
<idno type="doi">10.4204/EPTCS.146.13</idno>
<date when="2014-04-05">2014-04-05</date>
<idno type="wicri:Area/Hal/Corpus">001051</idno>
<idno type="wicri:Area/Hal/Curation">001051</idno>
<idno type="wicri:Area/Hal/Checkpoint">000B61</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">000B61</idno>
<idno type="wicri:Area/Main/Merge">000C25</idno>
<idno type="wicri:Area/Main/Curation">000C19</idno>
<idno type="wicri:Area/Main/Exploration">000C19</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Automata Techniques for Epistemic Protocol Synthesis</title>
<author><name sortKey="Aucher, Guillaume" sort="Aucher, Guillaume" uniqKey="Aucher G" first="Guillaume" last="Aucher">Guillaume Aucher</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-419153" status="VALID"><idno type="RNSR">198018249C</idno>
<orgName>Inria Rennes – Bretagne Atlantique </orgName>
<desc><address><addrLine>Campus de beaulieu35042 Rennes cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/centre/rennes</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-300009" type="direct"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Maubert, Bastien" sort="Maubert, Bastien" uniqKey="Maubert B" first="Bastien" last="Maubert">Bastien Maubert</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-206040" status="VALID"><idno type="IdRef">067077927</idno>
<idno type="RNSR">198912571S</idno>
<idno type="IdUnivLorraine">[UL]RSI--</idno>
<orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName>
<orgName type="acronym">LORIA</orgName>
<date type="start">2012-01-01</date>
<desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.loria.fr</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-413289" type="direct"></relation>
<relation name="UMR7503" active="#struct-441569" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-300009" type="direct"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-413289" type="direct"><org type="institution" xml:id="struct-413289" status="VALID"><idno type="IdRef">157040569</idno>
<idno type="IdUnivLorraine">[UL]100--</idno>
<orgName>Université de Lorraine</orgName>
<orgName type="acronym">UL</orgName>
<date type="start">2012-01-01</date>
<desc><address><addrLine>34 cours Léopold - CS 25233 - 54052 Nancy cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-lorraine.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR7503" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="ISNI">0000000122597504</idno>
<idno type="IdRef">02636817X</idno>
<orgName>Centre National de la Recherche Scientifique</orgName>
<orgName type="acronym">CNRS</orgName>
<date type="start">1939-10-19</date>
<desc><address><country key="FR"></country>
</address>
<ref type="url">http://www.cnrs.fr/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Nancy</settlement>
<settlement type="city">Metz</settlement>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
</placeName>
<orgName type="university">Université de Lorraine</orgName>
</affiliation>
</author>
<author><name sortKey="Pinchinat, Sophie" sort="Pinchinat, Sophie" uniqKey="Pinchinat S" first="Sophie" last="Pinchinat">Sophie Pinchinat</name>
<affiliation wicri:level="1"><hal:affiliation type="institution" xml:id="struct-105160" status="VALID"><orgName>Université de Rennes 1</orgName>
<orgName type="acronym">UR1</orgName>
<desc><address><addrLine>2 rue du Thabor - CS 46510 - 35065 Rennes cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-rennes1.fr/</ref>
</desc>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
</analytic>
<idno type="DOI">10.4204/EPTCS.146.13</idno>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">In this work we aim at applying automata techniques to problems studied in Dynamic Epistemic Logic, such as epistemic planning. To do so, we first remark that repeatedly executing ad infinitum a propositional event model from an initial epistemic model yields a relational structure that can be finitely represented with automata. This correspondence, together with recent results on uniform strategies, allows us to give an alternative decidability proof of the epistemic planning problem for propositional events, with as by-products accurate upper-bounds on its time complexity, and the possibility to synthesize a finite word automaton that describes the set of all solution plans. In fact, using automata techniques enables us to solve a much more general problem, that we introduce and call epistemic protocol synthesis.</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
</country>
<region><li>Grand Est</li>
<li>Lorraine (région)</li>
</region>
<settlement><li>Metz</li>
<li>Nancy</li>
</settlement>
<orgName><li>Université de Lorraine</li>
</orgName>
</list>
<tree><country name="France"><noRegion><name sortKey="Aucher, Guillaume" sort="Aucher, Guillaume" uniqKey="Aucher G" first="Guillaume" last="Aucher">Guillaume Aucher</name>
</noRegion>
<name sortKey="Maubert, Bastien" sort="Maubert, Bastien" uniqKey="Maubert B" first="Bastien" last="Maubert">Bastien Maubert</name>
<name sortKey="Pinchinat, Sophie" sort="Pinchinat, Sophie" uniqKey="Pinchinat S" first="Sophie" last="Pinchinat">Sophie Pinchinat</name>
</country>
</tree>
</affiliations>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000C19 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000C19 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Lorraine |area= InforLorV4 |flux= Main |étape= Exploration |type= RBID |clé= Hal:hal-01098740 |texte= Automata Techniques for Epistemic Protocol Synthesis }}
This area was generated with Dilib version V0.6.33. |